package com.example.javamaday.leetcode;

/**
 * 爬楼梯
 */
public class LeetCodeTest0070 {

    public static void main(String[] args) {

    }

    /**
     * 学会问题的分拆 - 找到最近重复子问题
     * 如： 1  --  1
     * 2  -- 2
     * 3 上3级的方式就为 上1 和 上2的方式的总和
     * 4 上4级的方式就为 上3 和 上2的方式的总和
     */
    public int climbStairs(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] result = new int[n + 1];
        result[1] = 1;
        result[2] = 2;
        for (int i = 3; i <= n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n];
    }
}
